# -*- coding:utf-8 -*-
__author__ = 'gin.chen'

"""
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
"""


# 第一版 未通过 超时
# def start_count(s):
#     # a = list(a)
#     # s = list()
#     my_set = set()
#     max_length, tmp_max = 0, 0
#     for i in range(0, len(s)):
#         for j in range(i, len(s)):
#             if s[j] not in my_set:
#                 my_set.add(s[j])
#                 tmp_max = len(my_set)
#             else:
#                 break
#         max_length = max(max_length, tmp_max)
#         my_set.clear()
#     return max_length
#
# 第二版
# def start_count(s):
#     my_set = set()
#     l_index, r_index, s_length, max_length = 0, 0, len(s), 0
#     while l_index < s_length and r_index < s_length:
#         if s[r_index] not in my_set:
#             my_set.add(s[r_index])
#             r_index += 1
#             max_length = max(max_length, r_index - l_index)
#         else:
#             my_set.remove(s[l_index])
#             l_index += 1
#     return max_length
# 第三版
def start_count(s):
    my_dict = dict()
    l_index, r_index, s_length, max_length = 0, 0, len(s), 0
    while r_index < s_length:
        if my_dict.has_key(s[r_index]):
            l_index = max(my_dict.get(s[r_index]), l_index)
        max_length = max(max_length, r_index - l_index + 1)
        my_dict[s[r_index]] = r_index + 1
        r_index += 1
    return max_length


if __name__ == '__main__':
    a = 'abcdefaghdds'
    # a = 'abcabcbb'
    print start_count(a)
